#include <vector>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>

using namespace std;


class Solution {
public:

    // 1658. 将 x 减到 0 的最小操作数
    // https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/
    int minOperations(vector<int>& nums, int x) {
        int sum = 0;
        for (const auto& num : nums)
        {
            sum += num;
        }
        if (sum - x < 0) return -1;

        int left = 0, right = 0;
        int target = 0;
        int ans = -1;
        while (right < nums.size())
        {
            target += nums[right];
            while (target > sum - x)
            {
                target -= nums[left++];
            }
            if (target == sum - x)
                ans = max(ans, right - left + 1);
            ++right;
        }

        return ans==-1 ? -1 : nums.size() - ans;
    }

    // 904. 水果成篮
    // https://leetcode.cn/problems/fruit-into-baskets/description/
    int totalFruit(vector<int>& fruits) {
        unordered_map<int, int> hash;
        int left = 0, right = 0;
        int ans = 0;

        while (right < fruits.size())
        {
            ++hash[fruits[right]];
            while (hash.size() > 2)
            {
                --hash[fruits[left]];
                if (hash[fruits[left]] == 0)
                    hash.erase(fruits[left]);
                ++left;
            }
            ans = max(ans, right - left + 1);
            ++right;
        }
        return ans;
    }

    // 优化
    // int totalFruit(vector<int>& fruits) {
    //     int hash[100001] = { 0 };
    //     int left = 0, right = 0;
    //     int ans = 0;
    //     int kind = 0;

    //     while (right < fruits.size())
    //     {
    //         if (hash[fruits[right]] == 0) ++kind;

    //         ++hash[fruits[right]];
    //         while (kind > 2)
    //         {
    //             --hash[fruits[left]];
    //             if (hash[fruits[left]] == 0)
    //                 --kind;
    //             ++left;
    //         }
    //         ans = max(ans, right - left + 1);
    //         ++right;
    //     }
    //     return ans;
    // }

    // 438. 找到字符串中所有字母异位词
    // https://leetcode.cn/problems/find-all-anagrams-in-a-string
    // bool chack(char *hash1, char *hash2)
    // {
    //     for (int i = 0; i<26; ++i)
    //     {
    //         if (hash1[i] != hash2[i])
    //             return false;
    //     }
    //     return true;
    // }

    // vector<int> findAnagrams(string s, string p) {
    //     if (p.size() > s.size()) return {};
    //     char phash[26] = { 0 };
    //     for (auto ch : p) ++phash[ch-'a'];

    //     char shash[26] = { 0 };
    //     int left = 0, right = 0;
    //     vector<int> ans;

    //     while (right < p.size() - 1)
    //     {
    //         ++shash[s[right++] - 'a'];
    //     }

    //     while (right < s.size())
    //     {
    //         ++shash[s[right] - 'a'];
    //         if (chack(shash, phash))
    //         {
    //             ans.push_back(left);
    //         }
    //         --shash[s[left++] - 'a'];
    //         ++right;
    //     }

    //     return ans;
    // }

    // 优化：
    vector<int> findAnagrams(string s, string p) {
        if (p.size() > s.size()) return {};

        int phash[26] = { 0 };
        for (auto ch : p) ++phash[ch-'a'];

        int shash[26] = { 0 };
        int left = 0, right = 0;
        int cnt = 0;

        vector<int> ans;
        
        while (right < s.size())
        {
            char in = s[right];
            ++shash[in - 'a'];
            if (shash[in - 'a'] <= phash[in - 'a'])
                ++cnt;
            if (right - left + 1 > p.size())
            {
                char out = s[left++];
                if (shash[out - 'a'] <= phash[out - 'a'])
                    --cnt;
                --shash[out - 'a'];
            }
            if (cnt == p.size())
                ans.push_back(left);
            ++right;
        }
        return ans;
    }

};